package com.zhupf.stack;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author zhupf
 * @date 2024年12月10日 11:19
 * @Description  again
 *
 *  85. 最大矩形
 * 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
 * <p>
 * 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
 * 输出：6
 * 解释：最大矩形如上图所示。
 */
public class MaximalRectangle {

    public static void main(String[] args) {
        char[][] matrix = {{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};
        System.out.println(maximalRectangle(matrix));
    }

    public static int maximalRectangle(char[][] matrix) {
        int[][] materixTmp = new int[matrix.length][matrix[0].length];
        int len = matrix[0].length;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < len; j++) {
                if (matrix[i][j] == '1') {
                    materixTmp[i][j] = (i == 0 ? 0 : materixTmp[i - 1][j]) + 1;
                }
            }
        }
        int ans = 0;
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < materixTmp.length; i++) {
            for (int j = 0; j < materixTmp[i].length; j++) {
                int cur = materixTmp[i][j];
                while (!deque.isEmpty() && cur <=materixTmp[i][deque.peek()]) {
                    Integer pop = deque.pop();
                    ans = Math.max(ans, materixTmp[i][pop] * ((j - pop) + (deque.isEmpty() ? pop : (pop - deque.peek() - 1))));
                }
                deque.push(j);
            }
            while (!deque.isEmpty()) {
                Integer pop = deque.pop();
                ans = Math.max(ans, materixTmp[i][pop] * ((len - pop) + (deque.isEmpty() ? pop : (pop - deque.peek() - 1))));
            }
        }
        return ans;
    }
}
